// https://leetcode.cn/problems/valid-triangle-number/

// 题干:给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

// 示例:输入: nums = [2,2,3,4]
//      输出: 3

// 碎语:观察题目，每个数字相互独立，即使值相同，只要位置不同也被认为不同
//      三元组的组合，与数字在数组里的位置无关
//      因此先从小到大排序，此时a+b>c就可以形成一个三角形
//      虽然题目说明nums[i]可能为0，但是排序后0+a<=b，永远不会被判为三角形，故无影响
//      排序后，怎么利用有序的特征来简化时间？
//      动中取静，先固定某个点来突破问题

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int triangleNumber(vector<int>& nums)
    {
        int ret = 0;
        sort(nums.begin(), nums.end());

        // 先固定一个最大的数
        for (int i = nums.size() - 1; i >= 2 ; i--){
            // 对撞指针
            int right = i - 1, left = 0;

            while (left != right){
                if (nums[left] + nums[right] > nums[i]){
                    // 此是可以构成三角形，那么a取[left,right)都能满足要求
                    ret += right - left;
                    right--;
                }
                // 若不能构成三角形，再让left自加
                else left++;
            }
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {4,2,3,4};

    cout << sol.triangleNumber(nums) << endl;

    return 0;
}